CS 5010: Problem Set 8

Out: Monday, November 3, 2014

Due: Monday, November 10, 2014 at 600pm.

The goal of this problem set is to give you practice using general recursion and invariants.

Remember that you must follow the design recipe.

For each function that you write using general recursion, you must be prepared to identify:

which are the trivial cases
for each non-trivial case, where and how you divided the problem into sub-problems.
for each non-trivial case, how you built the solution to the original problem from the solutions to the subproblems.
for each non-trivial case, whether or not it recurs on a substructure of one of the arguments.

Remember that every function that uses general recursion must have either a halting measure (if it always halts) or a comment that it sometimes does not halt (and a description of the cases in which it does not halt. I don't believe there are any functions on this problem set that should sometimes fail to terminate.

It is ok for a function using general recursion to call itself via a help function. If so, you need make sure that your halting measure decreases on EVERY recursive call to the function, even if that call comes via a help function.

As before, if your function does not fulfill its purpose for all combinations of arguments that satisfy the contract, then you must write an invariant that documents what additional assumptions your function makes about its arguments.

If you have two values of compound type, you may decompose both of them at once. For example, you may write something like

STRATEGY: structural decomposition on Ball
(define (some-fn b1 b2)
  (some-code (ball-x b1) (ball-y b1) (ball-x b2) (ball-y b2)))

You don't need to write a separate template for this. The structs need not be of the same type.

Write a paragraph or two near the top of your file, explaining your approach and what you did so that the TA will be able to understand your algorithm BEFORE READING ANY OF THE CODE. You may also wish to write such introductions to major sections of your file.

You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use refactoring to avoid duplication whenever it is helpful. Use list abstractions like filter, fold, and map whenever they are helpful. As in past problems, you will be penalized if you fail to see clear occasions for their use.

Required Exercises

You have probably seen some of the classic puzzles about pouring from one pitcher to another. Here are two examples:

Here we have an eight-quart pitcher filled with juice, an empty five-quart pitcher, and an empty three-quart pitcher. The pitchers are unmarked, and your task is to divide the eight quarts of juice so that both the five-quart pitcher and the eight-quart pitcher are each holding exactly four quarts.

On the counter we have a 10-quart pitcher full of milk, an empty seven-quart pitcher, and an empty three-quart pitcher. The pitchers are unmarked, and your task is to divide the 10 quarts of milk so that both the 10-quart pitcher and the seven-quart pitcher are each holding exactly five quarts.

A move in the game consists of pouring the liquid from one pitcher to another until the first pitcher is empty, or the second pitcher is full, whichever comes first.

The initial state of the game consists of a non-empty list of pitchers, each with their capacities. The pitchers are numbered starting from 1. The first pitcher in the list is filled to capacity and the others are empty. The goal of the game is expressed as a number, and the object of the game is to get one pitcher that holds exactly that amount of liquid.

For this problem, you are to write a simulation of a set of pitchers.

You must define a data type PitchersInternalRep that your simulation will use to represent a set of pitchers. This can be any representation you like.

However, in order for your program to communicate with the outside world (that is, our grading program), we will define a standard external representation. This representation is defined as follows:

PitchersExternalRep ::= ((capacity1 contents1)
                         (capacity2 contents2)
                         ...
                         (capacity_n contents_n))
WHERE:  n >=1, and for each i, 0 <= contents_i <= capacity_i
INTERPRETATION: the list of pitchers, from 1 to n, with their contents
and capacity
EXAMPLE: ((10 5) (8 7)) is a list of two pitchers.  The first has
capacity 10 and currently holds 5; the second has capacity 8 and
currently holds 7.

(define-struct move (src tgt))
A Move is a (make-move PosInt PosInt)
WHERE: src and tgt are different
INTERP: (make-move i j) means pour from pitcher i to pitcher j.
'pitcher i' refers to the i-th pitcher in the PitchersExternalRep.

You may define the data type PitchersInternalRep any way you like. It may or may not be the same as PitchersExternalRep. Using PitchersExternalRep as your internal representation makes some things easier and some things harder.

Provide the following functions:

list-to-pitchers : PitchersExternalRep -> PitchersInternalRep
RETURNS: your internal representation of the given input.

pitchers-to-list : PitchersInternalRep -> PitchersExternalRep
GIVEN: an internal representation of a set of pitchers
RETURNS: a PitchersExternalRep that represents them.

pitchers-after-moves : PitchersInternalRep ListOf<Move> -> PitchersInternalRep
GIVEN: An internal representation of a set of pitchers, and a sequence
of moves
WHERE: every move refers only to pitchers that are in the set of pitchers.
RETURNS: the internal representation of the set of pitchers that should
result after executing the given list of moves, in order, on the given
set of pitchers.

make-move : PosInt PosInt -> Move
WHERE: the two arguments are not equal
RETURNS: a move with the given numbers as its source and target,
respectively. 

move-src : Move -> PosInt
move-tgt : Move -> PosInt
RETURNS: the pitcher numbers of the source or target of the move.

Write a solver for pitcher problems like the ones above. You must provide the following function:
```
solution : NEListOf<PosInt> PosInt -> Maybe<ListOf<Move>>
GIVEN: a list of the capacities of the pitchers and the goal amount
RETURNS: a sequence of moves which, when executed from left to right,
results in one pitcher (not necessarily the first pitcher) containing
the goal amount.  Returns false if no such sequence exists.
```
Remember that initially the first pitcher is filled to capacity and the others are empty.

For example, the puzzles at the beginning of the problem would be expressed as the function calls
```
(solution (list 8 5 3) 4)
(solution (list 10 7 3) 5)
```
Turn in your solution to the first two questions as a single file called pitchers.rkt . As usual, before you turn in your solution, make sure it passes the tests in ps08-pitchers-qualification.rkt. As before, download this file, save it in your set08 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.
Extend your system to handle problems like the following ones:
You are at the side of a river. You have a three-liter pitcher and a seven-liter pitcher. The pitchers do not have markings to allow measuring smaller quantities. You need two liters of water. How can you measure two liters?

You are at the side of a river. You have a two-liter pitcher, a five-liter pitcher, and a ten-liter pitcher. The pitchers do not have markings to allow measuring smaller quantities. You need one liter of water. How can you measure one liter?

Your extended version should supply the same functions as the ones in the preceding problem, except that the initial configuration for solution has all the pitchers empty, and the possible moves are extended as follows:
```
(define-struct fill (pitcher))
(define-struct dump (pitcher))

A Move is one of
-- (make-move i j)    --pour the contents of pitcher i into pitcher j
-- (make-fill i)      --fill pitcher i from the river
-- (make-dump i)      --dump the contents of pitcher i into the river.
```
Be sure to provide make-fill, make-dump, and their selectors.

Turn in your solution as a file called river.rkt.

As usual, before you turn in your solution, make sure it passes the tests in ps08-river-qualification.rkt. As before, download this file, save it in your set08 directory, and run it to qualify your program for grading. Be sure to commit this file to repository so we know that you've done this correctly.

Last modified: Mon Nov 10 13:18:19 Eastern Standard Time 2014